#include "../tools.h"

/**
 * 
 * 二叉选择，先序遍历
 * 
 * 注意：如果取左首元素作为基准，则应先右后左地移动两侧指针
 * 因为归位操作是将指针重合处交换到左侧基准处，所以两指针必须在小于基准元素处相遇
 * 右侧指针停止的条件是遇到小于基准的元素
 * 左侧指针停止的条件是遇到大于基准的元素
 * 
 * 注意：与基准交换时要做检查
 * 因为可能只有两个元素，导致没有和基准做比较就跳出循环了
 */

// 递归，所以要用参数划定边界
void quick_sort(vector<int>& arr, int left, int right);

int main(int argc, char const *argv[])
{
    // vector<int> nums = {6, 2, 1, 7, 9, 3, 4, 5, 10, 8};
    // vector<int> nums = {-1,0,3,3,5,9,9,9,12};
    vector<int> nums = {12, 9, 9, 9, 5, 3, 3, 0, -1};

    quick_sort(nums, 0, nums.size() - 1);
    show(nums);

    return 0;
}

// 二叉选择，先序遍历
void quick_sort(vector<int>& arr, int left, int right){
    // 递归基 - 需要双指针，所以不能 ==
    if(left >= right) return;

    // 做事：捡出两侧元素 + 基准归位
    int base = left;
    int p1 = left + 1, p2 = right;
    while(p1 < p2){ // p1 == p2 时停
        while(p1 < p2 && arr[base] <= arr[p2]) --p2; // ！先右后左，非常重要
        while(p1 < p2 && arr[base] >= arr[p1]) ++p1;
        if(p1 < p2) swap(arr[p1], arr[p2]);
    }
    if(arr[p1] < arr[base]) {
        swap(arr[p1], arr[base]); // 可能只有两个元素，没有比较就跳出循环到这步了
        base = p1;
    }

    quick_sort(arr, left, base - 1);
    quick_sort(arr, base + 1, right);
}

